{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Concatenated Words"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #trie #array #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #字典树 #数组 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findAllConcatenatedWordsInADict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #连接词"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <strong>不含重复 </strong>单词的字符串数组 <code>words</code> ，请你找出并返回 <code>words</code> 中的所有 <strong>连接词</strong> 。</p>\n",
    "\n",
    "<p><strong>连接词</strong> 定义为：一个完全由给定数组中的至少两个较短单词（不一定是不同的两个单词）组成的字符串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [\"cat\",\"cats\",\"catsdogcats\",\"dog\",\"dogcatsdog\",\"hippopotamuses\",\"rat\",\"ratcatdogcat\"]\n",
    "<strong>输出：</strong>[\"catsdogcats\",\"dogcatsdog\",\"ratcatdogcat\"]\n",
    "<strong>解释：</strong>\"catsdogcats\" 由 \"cats\", \"dog\" 和 \"cats\" 组成; \n",
    "     \"dogcatsdog\" 由 \"dog\", \"cats\" 和 \"dog\" 组成; \n",
    "     \"ratcatdogcat\" 由 \"rat\", \"cat\", \"dog\" 和 \"cat\" 组成。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [\"cat\",\"dog\",\"catdog\"]\n",
    "<strong>输出：</strong>[\"catdog\"]</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= words.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= words[i].length &lt;= 30</code></li>\n",
    "\t<li><code>words[i]</code>&nbsp;仅由小写英文字母组成。&nbsp;</li>\n",
    "\t<li><code>words</code>&nbsp;中的所有字符串都是 <strong>唯一</strong> 的。</li>\n",
    "\t<li><code>1 &lt;= sum(words[i].length) &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [concatenated-words](https://leetcode.cn/problems/concatenated-words/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [concatenated-words](https://leetcode.cn/problems/concatenated-words/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"cat\",\"cats\",\"catsdogcats\",\"dog\",\"dogcatsdog\",\"hippopotamuses\",\"rat\",\"ratcatdogcat\"]', '[\"cat\",\"dog\",\"catdog\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "    def can_form_word(word):\n",
    "      n = len(word)\n",
    "      if n == 0:\n",
    "        return False\n",
    "      dp = [False] * (n + 1)\n",
    "      dp[0] = True\n",
    "      for i in range(1, n + 1):\n",
    "        for j in range(i):\n",
    "          if dp[j] and word[j:i] in word_set:\n",
    "            dp[i] = True\n",
    "            break\n",
    "      return dp[n]\n",
    "\n",
    "    words.sort(key=lambda x: len(x))\n",
    "    word_set = set()\n",
    "    ans = []\n",
    "    for word in words:\n",
    "      if can_form_word(word):\n",
    "        ans.append(word)\n",
    "      word_set.add(word)\n",
    "    return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        ws = set(words)\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            '''\n",
    "            判断每个单词能否完全被其他单词分割\n",
    "            '''\n",
    "            n = len(word)\n",
    "            # -1 代表无效, 如果一个字符串不能被words中的单词分割, 那就是无效的\n",
    "            f = [0] + [-1] * n\n",
    "            for i in range(1, n+1):\n",
    "                for j in range(i-1, -1, -1):\n",
    "                    if f[j] == -1: continue\n",
    "                    sub = word[j:i]\n",
    "                    if sub in ws:\n",
    "                        f[i] = max(f[i], f[j]+1)\n",
    "            if f[-1] > 1:\n",
    "                ans.append(word)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        res, wordDict = [], set(words)\n",
    "        def dp(s):\n",
    "            n = len(s)\n",
    "            dp = [True] + [False] * n\n",
    "            for i in range(n + 1):\n",
    "                for j in range(i + 1, n + 1):\n",
    "                    if dp[i] and s[i:j] in wordDict:\n",
    "                        dp[j] = True\n",
    "            return dp[-1]\n",
    "\n",
    "        for s in words:\n",
    "            wordDict.remove(s)\n",
    "            if dp(s):\n",
    "                res.append(s)\n",
    "            wordDict.add(s)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        \"\"\"\n",
    "        139. 单词拆分 的进阶\n",
    "        连接词不能是他自己\n",
    "        \"\"\"\n",
    "\n",
    "        wordSet = set(words)\n",
    "        ret = []\n",
    "        for word in words:\n",
    "            l = len(word)\n",
    "            dp = [0 for _ in range(l+1)]\n",
    "            for i in range(l+1):\n",
    "                if i == 0:\n",
    "                    dp[i] = 1\n",
    "                    continue\n",
    "                for j in range(i):\n",
    "                    if dp[j] != 0 and word[j:i] in wordSet:\n",
    "                        dp[i] = dp[j]+1\n",
    "                        continue\n",
    "            if dp[-1] > 2:\n",
    "                ret.append(word)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        words.sort(key=len)\n",
    "        prev = set()\n",
    "        res = []\n",
    " \n",
    "        \n",
    "        def check(word, prev):\n",
    "            if not prev: return False\n",
    "            n = len(word)\n",
    "            dp = [False] * (n + 1)\n",
    "            dp[0] = True\n",
    "            for i in range(1, n + 1):\n",
    "                for j in range(i):\n",
    "                    if not dp[j]: continue\n",
    "                    if word[j:i] in prev:\n",
    "                        dp[i] = True\n",
    "                        break\n",
    "            return dp[-1]\n",
    "\n",
    "        for word in words:\n",
    "            if check(word, prev):\n",
    "                res.append(word)\n",
    "            prev.add(word)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        n = len(words) \n",
    "        f = defaultdict(list) \n",
    "        for word in words:\n",
    "            f[word[0]].append(word) \n",
    "            f[word[0]].sort() \n",
    "        @cache \n",
    "        def dfs(word):\n",
    "            if word == '':\n",
    "                return 0\n",
    "            c = word[0]\n",
    "            m = len(word)\n",
    "            vec = f[c]\n",
    "            d = float('-inf')\n",
    "            for i in range(m, 0, -1):\n",
    "                idx = bisect.bisect_left(vec, word[:i]) \n",
    "                if idx < len(vec) and vec[idx] == word[:i]:\n",
    "                    d = max(d, dfs(word[i:]) + 1)\n",
    "                    if d >= 2:\n",
    "                        break \n",
    "            return d \n",
    "        ans = [] \n",
    "        for word in words:\n",
    "            if dfs(word) >= 2:\n",
    "                ans.append(word) \n",
    "        return ans           \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        def check_word(word, pre_dict):\n",
    "            if len(word) == 0:\n",
    "                return True\n",
    "            cur_dict = pre_dict\n",
    "            for index, c in enumerate(word):\n",
    "                cur_dict = cur_dict.get(c, None)\n",
    "                if cur_dict is None:\n",
    "                    return False\n",
    "                if cur_dict.get('end', 0) == 1:\n",
    "                    # 当前字符串前缀与树中单词匹配，递归搜索\n",
    "                    if check_word(word[index+1:], pre_dict):\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        words.sort(key=lambda x: len(x))\n",
    "        ans = []\n",
    "        pre_dict = {}\n",
    "        for item in words:\n",
    "            if len(item) == 0:\n",
    "                continue\n",
    "            if check_word(item, pre_dict):\n",
    "                ans.append(item)\n",
    "            else:\n",
    "                # insert word\n",
    "                cur_dict = pre_dict\n",
    "                for c in item:\n",
    "                    if cur_dict.get(c, None) is None:\n",
    "                        cur_dict[c] = {}\n",
    "                    cur_dict = cur_dict.get(c)\n",
    "                cur_dict['end'] = 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        vis = set(words)\n",
    "        ret = []\n",
    "        for word in words:\n",
    "            n = len(word)\n",
    "            @cache\n",
    "            def f(i):\n",
    "                if i == n: return 0\n",
    "                ans = -inf\n",
    "                for j in range(i, n):\n",
    "                    if word[i:j + 1] not in vis:\n",
    "                        continue\n",
    "                    ans = max(ans, 1 + f(j + 1))\n",
    "                return ans\n",
    "            \n",
    "            if f(0) > 1:\n",
    "                ret.append(word)\n",
    "        \n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        trie = {'?': False}\n",
    "        def add(w):\n",
    "            cur  = trie\n",
    "            for x in w:\n",
    "                if x not in cur:\n",
    "                    cur[x] = {'?': False}\n",
    "                cur = cur[x]\n",
    "            cur['?'] = True\n",
    "        words.sort(key = len)\n",
    "        ans = []\n",
    "        for w in words:\n",
    "            nodes = [trie]\n",
    "            for c in w:\n",
    "                nxt = []\n",
    "                add_root = False\n",
    "                for node in nodes:\n",
    "                    if c in node:\n",
    "                        nxt.append(node[c])\n",
    "                        if node[c]['?']:\n",
    "                            add_root = True\n",
    "                if add_root:\n",
    "                    nxt.append(trie)\n",
    "                nodes = nxt\n",
    "            if any(x['?'] for x in nodes):\n",
    "                ans.append(w)\n",
    "            add(w)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.lookup = {}\n",
    "\n",
    "    def insert(self, word):\n",
    "        node = self.lookup\n",
    "        for char in word:\n",
    "            node = node.setdefault(char, {})\n",
    "        node['#'] = '#'\n",
    "\n",
    "    def search(self, word):\n",
    "        node = self.lookup\n",
    "        for char in word:\n",
    "            if char not in node:\n",
    "                return False\n",
    "            node = node[char]\n",
    "        return '#' in node\n",
    "    def dfs(self,word,pos,visted):\n",
    "        if not word or pos>=len(word):\n",
    "            return True\n",
    "        if visted[pos]:\n",
    "            return False\n",
    "        visted[pos] = True\n",
    "        for i in range(pos,len(visted)):\n",
    "            if self.search(word[pos:i+1]) and self.dfs(word,i+1,visted):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        words.sort(key=lambda x: len(x))\n",
    "        trie = Trie()\n",
    "        res = []\n",
    "        for word in words:\n",
    "            if trie.dfs(word,0,[False]*len(word)):\n",
    "                res.append(word)\n",
    "            else:\n",
    "                trie.insert(word)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        vis = set(words)\n",
    "        ret = []\n",
    "        for word in words:\n",
    "            n = len(word)\n",
    "            @cache\n",
    "            def f(i):\n",
    "                if i == n: return 0\n",
    "                ans = -inf\n",
    "                for j in range(i, n):\n",
    "                    if word[i:j + 1] not in vis:\n",
    "                        continue\n",
    "                    ans = max(ans, 1 + f(j + 1))\n",
    "                return ans\n",
    "            \n",
    "            if f(0) > 1:\n",
    "                ret.append(word)\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        vis = set(words)\n",
    "        ret = []\n",
    "        for word in words:\n",
    "            n = len(word)\n",
    "            @cache\n",
    "            def f(i):\n",
    "                if i == n: return 0\n",
    "                ans = -inf\n",
    "                for j in range(i, n):\n",
    "                    if word[i:j + 1] not in vis:\n",
    "                        continue\n",
    "                    ans = max(ans, 1 + f(j + 1))\n",
    "                return ans\n",
    "            \n",
    "            if f(0) > 1:\n",
    "                ret.append(word)\n",
    "        \n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def f(self, w: str, d: dict)->bool:        \n",
    "        if w in self.s: return True\n",
    "        for cnt, i in enumerate(w):\n",
    "            if i not in d: return False\n",
    "            d = d[i]\n",
    "            if '' in d and self.f(w[cnt+1:], self.d): return True\n",
    "        return False\n",
    "\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        words.sort(key = len)\n",
    "        self.d, self.s, res = {}, set(), []\n",
    "        for w in words:\n",
    "            if self.f(w, self.d): res.append(w)\n",
    "            else:\n",
    "                p = self.d            \n",
    "                for i in w:\n",
    "                    if i not in p: p[i] = {}\n",
    "                    p = p[i]\n",
    "                p[''] = None\n",
    "            self.s.add(w)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def f(self, w: str, d: dict)->bool:        \n",
    "        if self.flag: print(0, w)\n",
    "        if w in self.s: return True\n",
    "        for cnt, i in enumerate(w):\n",
    "            if i not in d: \n",
    "                if self.flag: print(1)\n",
    "                return False\n",
    "            d = d[i]\n",
    "            if '' in d:\n",
    "                if cnt == len(w)-1: return True\n",
    "                if self.f(w[cnt+1:], self.d): return True\n",
    "        if self.flag: print(2)\n",
    "        return False\n",
    "\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        words.sort(key = len)\n",
    "        self.d = {}\n",
    "        self.s = set()\n",
    "        res = []\n",
    "        self.flag = False\n",
    "        for w in words:\n",
    "            #self.flag = True if w == \"dogcatsdog\" else False\n",
    "            if self.f(w, self.d): res.append(w)\n",
    "            else:\n",
    "                p = self.d            \n",
    "                for i in w:\n",
    "                    if i not in p: p[i] = {}\n",
    "                    p = p[i]\n",
    "                p[''] = None\n",
    "            self.s.add(w)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        trie,ans=Trie(),[]\n",
    "        words.sort(key=len)\n",
    "        for c in words:\n",
    "            if c is \"\":\n",
    "                continue\n",
    "            if trie.find(c):\n",
    "                ans.append(c)\n",
    "            else:\n",
    "                trie.insert(c)\n",
    "        return ans\n",
    "                \n",
    "\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root={}\n",
    "\n",
    "    def insert(self,word):\n",
    "        node=self.root\n",
    "        for w in word+\"#\":\n",
    "            if w not in node:\n",
    "                node[w]={}\n",
    "            node=node[w]\n",
    "    \n",
    "    def find(self,word):\n",
    "        node=self.root\n",
    "        for i in range(len(word)):\n",
    "            if \"#\" in node:\n",
    "                if self.find(word[i:]):\n",
    "                    return  True\n",
    "            if word[i] in  node:\n",
    "                node = node[word[i]]\n",
    "            else:\n",
    "                return False\n",
    "        return \"#\" in node\n",
    "                    \n",
    "                    \n",
    "                                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        def helper(word: str, root: dict) -> bool:\n",
    "            if len(word) == 0:\n",
    "                return True\n",
    "            tree = root\n",
    "            for i,c in enumerate(word):\n",
    "                tree = tree.get(c, None)\n",
    "                if not tree:\n",
    "                    return False\n",
    "                if '#' in tree:\n",
    "                    if helper(word[i+1:], root):\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        def addWord(word: str) -> None:\n",
    "            tree = root\n",
    "            for c in word:\n",
    "                if c not in tree:\n",
    "                    tree[c] = {}\n",
    "                tree = tree[c]\n",
    "            tree['#'] = {}\n",
    "            \n",
    "        words.sort(key=lambda x: len(x))\n",
    "        ret = []\n",
    "        root = {}\n",
    "        for word in words:\n",
    "            if len(word)==0:\n",
    "                continue\n",
    "            if helper(word, root):\n",
    "                ret.append(word)\n",
    "            else:\n",
    "                addWord(word)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        trie,ans=Trie(),[]\n",
    "        for word in sorted(words, key=len):\n",
    "            if word==\"\":\n",
    "                continue\n",
    "            if trie.find(word):\n",
    "                ans.append(word)\n",
    "            else:\n",
    "                trie.insert(word)\n",
    "        return ans\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root={}\n",
    "    \n",
    "    def insert(self,word):\n",
    "        node=self.root\n",
    "        for w in word+\"#\":\n",
    "            if w not in node:\n",
    "                node[w]={}\n",
    "            node=node[w]\n",
    "    \n",
    "    def find(self,word):\n",
    "        node=self.root\n",
    "        for i in range(len(word)):\n",
    "            if \"#\" in node:\n",
    "                if self.find(word[i:]):\n",
    "                    return True\n",
    "            if word[i] in node:\n",
    "                node=node[word[i]]\n",
    "            else:\n",
    "                return False\n",
    "        return \"#\" in node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        words = sorted(words, key=len)\n",
    "        w_map = {}\n",
    "        res = []\n",
    "        def check_con(word, w_map, conF):\n",
    "            if len(word) == 0:\n",
    "                return True\n",
    "            ans = False\n",
    "            search_f = True\n",
    "            cur_map = w_map\n",
    "            for i, c in enumerate(word):\n",
    "                if c in cur_map:\n",
    "                    cur_map = cur_map[c]\n",
    "                    if '#' in cur_map and search_f:\n",
    "                        ans |= check_con(word[i+1:], w_map, False)\n",
    "                        if ans:\n",
    "                            return ans\n",
    "                elif conF:\n",
    "                    search_f = False\n",
    "                    cur_map[c] = {}\n",
    "                    cur_map = cur_map[c]\n",
    "                else:\n",
    "                    search_f = False\n",
    "\n",
    "            if '#' not in cur_map and conF:\n",
    "                cur_map['#'] = {}\n",
    "\n",
    "            return ans\n",
    "\n",
    "        for word in words:\n",
    "            if check_con(word, w_map, True):\n",
    "                res.append(word)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        trie, ans = Trie(), []\n",
    "        for word in sorted(words, key=len):\n",
    "            if word == \"\":\n",
    "                continue\n",
    "            if trie.find(word):\n",
    "                ans.append(word)\n",
    "            else:\n",
    "                trie.insert(word)\n",
    "        return ans\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = {}\n",
    "    \n",
    "    def insert(self, word):\n",
    "        node = self.root\n",
    "        for w in word + \"#\":\n",
    "            if w not in node:\n",
    "                node[w] = {}\n",
    "            node = node[w]\n",
    "    \n",
    "    def find(self, word):\n",
    "        node = self.root\n",
    "        for i in range(len(word)):\n",
    "            if \"#\" in node:\n",
    "                if self.find(word[i:]):\n",
    "                    return True\n",
    "            if word[i] in node:\n",
    "                node = node[word[i]]\n",
    "            else:\n",
    "                return False\n",
    "        return \"#\" in node\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        n = len(words) \n",
    "        f = defaultdict(list) \n",
    "        for word in words:\n",
    "            f[word[0]].append(word) \n",
    "            f[word[0]].sort() \n",
    "        @cache \n",
    "        def dfs(word, d):\n",
    "            if word == '':\n",
    "                return d > 1\n",
    "            c = word[0]\n",
    "            m = len(word)\n",
    "            vec = f[c]\n",
    "            for i in range(m, 0, -1):\n",
    "                idx = bisect.bisect_left(vec, word[:i]) \n",
    "                if idx < len(vec) and vec[idx] == word[:i]:\n",
    "                    if dfs(word[i:], d+1 if d < 2 else 2):\n",
    "                        return True \n",
    "            return False \n",
    "        ans = [] \n",
    "        for word in words:\n",
    "            if dfs(word, 0):\n",
    "                ans.append(word) \n",
    "        return ans           \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        from sortedcontainers import SortedSet\n",
    "        atoms = SortedSet()\n",
    "        result = []\n",
    "        \n",
    "        def isConcatenated(word: str) -> bool:\n",
    "            if len(atoms) < 2:return False\n",
    "            \n",
    "            if atoms.count(word) == 1 : return True\n",
    "\n",
    "            n = len(word)\n",
    "            isCon = False\n",
    "            for i in range(n):\n",
    "                if atoms.count(word[0:i+1]):\n",
    "                    isCon = isConcatenated(word[i+1:])\n",
    "                if isCon: return isCon\n",
    "\n",
    "            return isCon\n",
    "        \n",
    "        # Sorted by len of word\n",
    "        words.sort(key = lambda i : len(i))\n",
    "        for word in words:\n",
    "            if isConcatenated(word):\n",
    "                result.append(word)\n",
    "            else:\n",
    "                atoms.add(word)\n",
    "\n",
    "        return result        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        from sortedcontainers import SortedSet\n",
    "        atoms = SortedSet()\n",
    "        result = []\n",
    "        \n",
    "        def isConcatenated(word: str) -> bool:\n",
    "            if len(atoms) < 2:return False\n",
    "            \n",
    "            if atoms.count(word) == 1 : return True\n",
    "\n",
    "            n = len(word)\n",
    "            isCon = False\n",
    "            for i in range(n):\n",
    "                if atoms.count(word[0:i+1]):\n",
    "                    isCon = isConcatenated(word[i+1:])\n",
    "                if isCon: return isCon\n",
    "\n",
    "            return isCon\n",
    "        \n",
    "        # Sorted by len of word\n",
    "        words.sort(key = lambda i : len(i))\n",
    "        for word in words:\n",
    "            if isConcatenated(word):\n",
    "                result.append(word)\n",
    "            else:\n",
    "                atoms.add(word)\n",
    "\n",
    "        return result        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        if len(words) == 1:\n",
    "            return []\n",
    "        s = set(words)\n",
    "        # 测试用例42有空string。。。\n",
    "        if \"\" in s:\n",
    "            s.remove(\"\")\n",
    "        min_word_length = min([len(w) for w in words])\n",
    "        @lru_cache()\n",
    "        def dfs(word):\n",
    "            for i in range(min_word_length, len(word) - min_word_length + 1):\n",
    "                if word[:i] in s and (word[i:] in s or dfs(word[i:])):\n",
    "                    return True\n",
    "            return False\n",
    "        ans = []\n",
    "        for w in words:\n",
    "            if dfs(w):\n",
    "                ans.append(w)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        if len(words) == 1:\n",
    "            return []\n",
    "        s = set(words)\n",
    "        if \"\" in s:\n",
    "            s.remove(\"\")\n",
    "        min_word_length = min([len(w) for w in words])\n",
    "\n",
    "        @lru_cache()\n",
    "        def dfs(w):\n",
    "            for i in range(min_word_length, len(w) - min_word_length + 1):\n",
    "                if w[:i] in s and (w[i:] in s or dfs(w[i:])):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        ans = []\n",
    "        for w in words:\n",
    "            if dfs(w):\n",
    "                ans.append(w)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        if len(words) == 1:\n",
    "            return []\n",
    "        s = set(words)\n",
    "        if \"\" in s:\n",
    "            s.remove(\"\")\n",
    "        min_word_length = min([len(w) for w in words])\n",
    "\n",
    "        @lru_cache()\n",
    "        def dfs(w):\n",
    "            for i in range(min_word_length, len(w) - min_word_length + 1):\n",
    "                if w[:i] in s and (w[i:] in s or dfs(w[i:])):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        ans = []\n",
    "        for w in words:\n",
    "            if dfs(w):\n",
    "                ans.append(w)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        words.sort(key=len)\n",
    "        min_len = max(1, len(words[0]))\n",
    "        prev = {}\n",
    "        res = []\n",
    "\n",
    "       # dic=set()\n",
    "        #print(mi)\n",
    "        #print(words)\n",
    "        @cache\n",
    "        \n",
    "        def check(word):\n",
    "            nonlocal prev\n",
    "            if  word in prev: \n",
    "                return prev[word]\n",
    "            for i in range(min_len, len(word) - min_len + 1):\n",
    "                if word[:i] in prev and (word[i:] in prev or (check(word[i:]))):\n",
    "                    prev[word]=True\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "\n",
    "        ans=[]\n",
    "        #print(check(0,\"catsdogcats\"))\n",
    "       # return []\n",
    "        for w in words:\n",
    "            if check(w):\n",
    "                ans.append(w)\n",
    "            prev[w]=True\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.child = {}\n",
    "        self.isEnd = False \n",
    "    \n",
    "    def insert(self, word):\n",
    "        t = self \n",
    "        for w in word:\n",
    "            idx = ord(w) - ord('a')\n",
    "            if t.child.get(idx, None) is None:\n",
    "                t.child[idx] = Trie()\n",
    "            \n",
    "            t = t.child[idx]\n",
    "        \n",
    "        t.isEnd = True\n",
    "\n",
    "    def search(self, word, start, visied):\n",
    "        if start == len(word):\n",
    "            return True \n",
    "\n",
    "        if visied[start]:\n",
    "            return False\n",
    "\n",
    "        visied[start] = True \n",
    "\n",
    "        t = self \n",
    "        for i in range(start, len(word)):\n",
    "            w = word[i]\n",
    "            idx = ord(w) - ord('a')\n",
    "            t = t.child.get(idx, None)\n",
    "            if t is None:\n",
    "                return False\n",
    "            \n",
    "            if t.isEnd and self.search(word, i + 1, visied):\n",
    "                return True\n",
    "        \n",
    "        return False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        words.sort(key=len)\n",
    "        res = []\n",
    "        trie = Trie()\n",
    "        for word in words:\n",
    "            if word == '':\n",
    "                continue \n",
    "            \n",
    "            if trie.search(word, 0, [False] * len(word)):\n",
    "                res.append(word)\n",
    "            else:\n",
    "                trie.insert(word)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\r\n",
    "    def __init__(self) -> None:\r\n",
    "        self.slots:dict[str,Trie]={}\r\n",
    "        self.is_end=False\r\n",
    "    \r\n",
    "    def insert(self,word):\r\n",
    "        cur=self\r\n",
    "        for ch in word:\r\n",
    "            cur=cur.slots.setdefault(ch,Trie())\r\n",
    "        cur.is_end=True\r\n",
    "    \r\n",
    "    def find(self,word,index,vis:list[bool]):\r\n",
    "        if len(word)==index:\r\n",
    "            return True\r\n",
    "        cur=self\r\n",
    "        if vis[index]:\r\n",
    "            return False\r\n",
    "        vis[index]=True\r\n",
    "        for i in range(index,len(word)):\r\n",
    "            ch=word[i]\r\n",
    "            cur=cur.slots.get(ch,None)\r\n",
    "            if not cur:\r\n",
    "                return False\r\n",
    "            if cur.is_end and self.find(word,i+1,vis):\r\n",
    "                return True\r\n",
    "        return False\r\n",
    "                \r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\r\n",
    "        words.sort(key=len)\r\n",
    "        root=Trie()\r\n",
    "        ret=[]\r\n",
    "        for word in words:\r\n",
    "            if root.find(word,0,[False]*len(word)):\r\n",
    "                ret.append(word)\r\n",
    "            else:\r\n",
    "                root.insert(word)\r\n",
    "        return ret\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node(object):\n",
    "    def __init__(self):\n",
    "        self.children = collections.defaultdict(Node)\n",
    "        self.isword = False \n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "    \n",
    "    def addWord(self, word: str):\n",
    "        current = self.root\n",
    "        for w in word:\n",
    "            current = current.children[w]\n",
    "        current.isword = True\n",
    "    \n",
    "    def match(self, root, word, index):\n",
    "        if root == None:\n",
    "            return False\n",
    "\n",
    "        if index == len(word):\n",
    "            return root.isword\n",
    "        \n",
    "\n",
    "        # if match a prefix, either go down or go back to top with the rest of the word\n",
    "        res1 = self.match(root.children.get(word[index]), word, index+1)\n",
    "\n",
    "        res2 = self.match(self.root, word[index:], 0) if root.isword else False\n",
    "            \n",
    "        return res1 or res2\n",
    "    \n",
    "    def searchConcat(self, word):\n",
    "        if self.match(self.root, word, 0):\n",
    "            return True\n",
    "        self.addWord(word)\n",
    "        return False\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        words = sorted(words, key=lambda x: len(x))\n",
    "        res = []\n",
    "        trie = Trie()\n",
    "        for word in words:\n",
    "            if trie.searchConcat(word):\n",
    "                res.append(word)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = collections.defaultdict(Trie)\n",
    "        self.end = False \n",
    "    def insert(self, word):\n",
    "        if not word: \n",
    "            self.end = True\n",
    "            return \n",
    "        child = self.children[word[0]]\n",
    "        child.insert(word[1:])\n",
    "    def dfs(self, word, i, vis):\n",
    "        if i==len(word): return True\n",
    "        if vis[i]:\n",
    "            return False\n",
    "        vis[i] = True\n",
    "        child = self \n",
    "        for j in range(i, len(word)):\n",
    "            c = word[j]\n",
    "            child = child.children.get(c)\n",
    "            if child is None: return False\n",
    "            if child.end and self.dfs(word, j+1, vis): return True\n",
    "        return False\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        # 前缀树+dfs搜索\n",
    "        words = sorted(words, key=lambda x: len(x))\n",
    "        trie = Trie()\n",
    "        res = []\n",
    "        for w in words:\n",
    "            if trie.dfs(w, 0, [False]*len(w)):\n",
    "                res.append(w)\n",
    "            trie.insert(w)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node(object):\n",
    "    def __init__(self):\n",
    "        self.children = collections.defaultdict(Node)\n",
    "        self.isword = False \n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "    \n",
    "    def addWord(self, word: str):\n",
    "        current = self.root\n",
    "        for w in word:\n",
    "            current = current.children[w]\n",
    "        current.isword = True\n",
    "    \n",
    "    def match(self, root, word, idx):\n",
    "        if root == None:\n",
    "            return False\n",
    "        \n",
    "        if idx == len(word):\n",
    "            return root.isword\n",
    "        \n",
    "        # if match a prefix, either go down or go back the top with the rest of the word\n",
    "        res1 = self.match(root.children.get(word[idx]), word, idx+1)\n",
    "        res2 = self.match(self.root, word[idx:], 0) if root.isword else False\n",
    "\n",
    "        return res1 or res2\n",
    "\n",
    "\n",
    "    def searchConcat(self, word):\n",
    "        if self.match(self.root, word, 0):\n",
    "            return True\n",
    "        self.addWord(word)\n",
    "        return False\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        words = sorted(words, key=lambda x: len(x))\n",
    "        res = []\n",
    "        \n",
    "        trie = Trie()\n",
    "        for word in words:\n",
    "            if trie.searchConcat(word):\n",
    "                res.append(word)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        #words.sort(key=lambda x:len(x))\n",
    "        s=set(words)\n",
    "        ret=[]\n",
    "        @cache\n",
    "        def dfs(w):\n",
    "            if not w:\n",
    "                return 1\n",
    "            for i in range(1,len(w)+1):\n",
    "                if w[:i] not in s:\n",
    "                    continue \n",
    "                tp=dfs(w[i:])\n",
    "                if tp>0:\n",
    "                    return 1+tp\n",
    "            return 0\n",
    "        for w in words:\n",
    "            if dfs(w)>2:\n",
    "                ret.append(w)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        s=set(words)\n",
    "        ret=[]\n",
    "        @cache\n",
    "        def dfs(w):\n",
    "            if not w:\n",
    "                return 1\n",
    "            for i in range(1,len(w)+1):\n",
    "                if w[:i] not in s:\n",
    "                    continue \n",
    "                tp=dfs(w[i:])\n",
    "                if tp>0:\n",
    "                    return 1+tp\n",
    "            return 0\n",
    "        for w in words:\n",
    "            if dfs(w)>2:\n",
    "                ret.append(w)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        words.sort(key=lambda x:len(x))\n",
    "        ls=[]\n",
    "        s=set(words)\n",
    "        #s=[]\n",
    "        ret=[]\n",
    "        @cache\n",
    "        def dfs(w):\n",
    "            #print(x,l,w)\n",
    "            if not w:\n",
    "                return 1\n",
    "            #if x>l:\n",
    "            #    return False\n",
    "            #find=False\n",
    "            #for child in s:\n",
    "            for i in range(1,len(w)+1):\n",
    "                if w[:i] not in s:\n",
    "                    continue \n",
    "                tp=dfs(w[i:])\n",
    "                if tp>0:\n",
    "                    return 1+tp\n",
    "            return 0\n",
    "        for w in words:\n",
    "            l=len(w)\n",
    "            if dfs(w)>2:\n",
    "                #print(w,dfs(w))\n",
    "                ret.append(w)\n",
    "            #s.add(w)\n",
    "            #else:\n",
    "            #    #s.add(w)\n",
    "            #    s.append(w)\n",
    "            #    if ls and ls[-1]!=l:\n",
    "            #        ls.append(l)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        wordSet = set(words)\n",
    "        res = []\n",
    "\n",
    "        \n",
    "        @functools.lru_cache(None)\n",
    "        def check(s):\n",
    "            n = len(s)\n",
    "            for i in range(1,n+1):\n",
    "                if s[:i] in wordSet:\n",
    "                    if check(s[i:]) or s[i:] in wordSet:\n",
    "                        return True\n",
    "            return False\n",
    "        for word in words:\n",
    "            if check(word):\n",
    "                res.append(word)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        words.sort(key=lambda x:len(x))\n",
    "        ls=[]\n",
    "        s=set(words)\n",
    "        ret=[]\n",
    "        @cache\n",
    "        def dfs(w):\n",
    "            if not w:\n",
    "                return 1\n",
    "            for i in range(1,len(w)+1):\n",
    "                if w[:i] not in s:\n",
    "                    continue \n",
    "                tp=dfs(w[i:])\n",
    "                if tp>0:\n",
    "                    return 1+tp\n",
    "            return 0\n",
    "        for w in words:\n",
    "            l=len(w)\n",
    "            if dfs(w)>2:\n",
    "                ret.append(w)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.isEnd = False\n",
    "\n",
    "    def insert(self, word: str):\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ch = ord(ch) - ord('a')\n",
    "            if not node.children[ch]:\n",
    "                node.children[ch] = Trie()\n",
    "            node = node.children[ch]\n",
    "        node.isEnd = True\n",
    "\n",
    "    def dfs(self, word: str, start: int, vis: List[bool]) -> bool:\n",
    "        if start == len(word):\n",
    "            return True\n",
    "        if vis[start]:\n",
    "            return False\n",
    "        vis[start] = True\n",
    "        node = self\n",
    "        for i in range(start, len(word)):\n",
    "            node = node.children[ord(word[i]) - ord('a')]\n",
    "            if node is None:\n",
    "                return False\n",
    "            if node.isEnd and self.dfs(word, i + 1, vis):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n",
    "'''\n",
    "字典树 + dfs\n",
    "'''\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        words.sort(key=len)\n",
    "\n",
    "        ans = []\n",
    "        root = Trie()\n",
    "        for word in words:\n",
    "            if word == \"\":\n",
    "                continue\n",
    "            if root.dfs(word, 0, [False] * len(word)):\n",
    "                ans.append(word)\n",
    "            else:\n",
    "                root.insert(word)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        words.sort(key=len)\n",
    "        trie = Trie()\n",
    "        ans = []\n",
    "        for word in words:\n",
    "            if word == \"\":\n",
    "                continue\n",
    "            if trie.findAllConcat(word, [False] * len(word)):\n",
    "                ans.append(word)\n",
    "            else:\n",
    "                trie.insert(word)\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.nodeList = [None] * 26\n",
    "        self.isWord = False\n",
    "\n",
    "    def insert(self, word: str):\n",
    "        cur = self\n",
    "        for c in word:\n",
    "            c = ord(c) - ord('a')\n",
    "            if not cur.nodeList[c]:\n",
    "                cur.nodeList[c] = Trie()\n",
    "            cur = cur.nodeList[c]\n",
    "        cur.isWord = True\n",
    "    \n",
    "    def findAllConcat(self, word: str, vis: List[bool],start = 0) -> bool:\n",
    "        n = len(word)\n",
    "        if start == len(word):\n",
    "            return True\n",
    "        if vis[start]:\n",
    "            return False\n",
    "        vis[start] = True\n",
    "        cur = self\n",
    "        base = ord('a')\n",
    "        for i in range(start, n):\n",
    "            if not cur.nodeList[ord(word[i]) - base]:\n",
    "                return False\n",
    "            if cur.nodeList[ord(word[i]) - base].isWord:\n",
    "                if self.findAllConcat(word, vis, i + 1):\n",
    "                    return True\n",
    "            cur = cur.nodeList[ord(word[i]) - base]\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None]*26\n",
    "        self.isend = False\n",
    "    \n",
    "    def insert(self,word):\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ind = ord(ch)-ord(\"a\")\n",
    "            if not node.children[ind]:\n",
    "                node.children[ind] = Trie()\n",
    "            node = node.children[ind]\n",
    "        node.isend = True\n",
    "\n",
    "    def dfs(self,word,start):\n",
    "        node = self\n",
    "        n = len(word)\n",
    "        if start==n:\n",
    "            return True\n",
    "        for i in range(start,n):\n",
    "            ind = ord(word[i])-ord(\"a\")\n",
    "            node = node.children[ind]\n",
    "            if not node:\n",
    "                return False\n",
    "            if node.isend and self.dfs(word,i+1):\n",
    "                return  True\n",
    "        return False\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        words.sort(key=lambda x:len(x))\n",
    "        res = []\n",
    "        root = Trie()\n",
    "        for word in words:\n",
    "            if word!=\"\":\n",
    "                if root.dfs(word,0):\n",
    "                    res.append(word)\n",
    "                else:\n",
    "                    root.insert(word)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie():\n",
    "    def __init__(self):\n",
    "        self.next=[None]*26\n",
    "        self.leaf=False\n",
    "    \n",
    "    def search(self, s):\n",
    "        if self.check(s): return True\n",
    "        for i in range(1,len(s)):\n",
    "            if self.check(s[:i]) and self.search(s[i:]): return True\n",
    "        return False\n",
    "\n",
    "    def check(self, s):\n",
    "        t=self\n",
    "        for i, c in enumerate(s):\n",
    "            if t.next[ord(c)-ord('a')] is not None:\n",
    "                t=t.next[ord(c)-ord('a')]\n",
    "            else:\n",
    "                return False\n",
    "        return t.leaf\n",
    "\n",
    "    def add(self, s):\n",
    "        t=self\n",
    "        for i, c in enumerate(s):\n",
    "            if t.next[ord(c)-ord('a')] is None:\n",
    "                t.next[ord(c)-ord('a')]=Trie()\n",
    "            t=t.next[ord(c)-ord('a')]\n",
    "        t.leaf=True\n",
    "        return\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words):\n",
    "        trie=Trie()\n",
    "        res=[]\n",
    "        # twords=copy.deepcopy(words)\n",
    "        words.sort(key=lambda x:len(x))\n",
    "        # print(words)\n",
    "        for word in words:\n",
    "            if trie.search(word):\n",
    "                res.append(word)\n",
    "            else:\n",
    "                trie.add(word)\n",
    "        return res\n",
    "        # print(res)\n",
    "        # print(twords)\n",
    "        # return list(filter(lambda x: x in res, twords))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.isEnd = False\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        current = self\n",
    "        for w in word:\n",
    "            w = ord(w) -ord('a')\n",
    "            if not current.children[w]:\n",
    "                current.children[w] = Trie()\n",
    "            current = current.children[w]\n",
    "        current.isEnd =True\n",
    "        \n",
    "\n",
    "    def dfs(self, word: str, start: int, vis: List[bool]) -> bool:\n",
    "        if start == len(word):\n",
    "            return True\n",
    "        if vis[start]:\n",
    "            return False\n",
    "        vis[start] = True\n",
    "        current = self\n",
    "        for i in range(start, len(word)):\n",
    "            current = current.children[ord(word[i]) - ord('a')]\n",
    "            if current is None:\n",
    "                return False\n",
    "            if current.isEnd and self.dfs(word, i + 1, vis):\n",
    "                return True \n",
    "        return False\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        words.sort(key=len)\n",
    "\n",
    "        ans = []\n",
    "        root = Trie()\n",
    "        for word in words:\n",
    "            if word == \"\":\n",
    "                continue\n",
    "            if root.dfs(word, 0, [False] * len(word)):\n",
    "                ans.append(word)\n",
    "            else:\n",
    "                root.insert(word)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        words_set = set(words)\n",
    "        dp = {}\n",
    "        def dfs(word):\n",
    "            if word in dp:\n",
    "                return dp[word]\n",
    "            for i in range(1, len(word)):\n",
    "                prefix = word[:i]\n",
    "                suffix = word[i:]\n",
    "                if (prefix in words_set and suffix in words_set) or (prefix in words_set and dfs(suffix)):\n",
    "                    dp[word] = True\n",
    "                    return dp[word]\n",
    "            dp[word] = False \n",
    "            return dp[word]\n",
    "\n",
    "\n",
    "        \n",
    "        res = []\n",
    "        for word in words:\n",
    "            if dfs(word):\n",
    "                res.append(word)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.isEnd = False\n",
    "\n",
    "    def insert(self, word: str):\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ch = ord(ch) - ord('a')\n",
    "            if not node.children[ch]:\n",
    "                node.children[ch] = Trie()\n",
    "            node = node.children[ch]\n",
    "        node.isEnd = True\n",
    "\n",
    "    def dfs(self, word: str, start: int, vis: List[bool]) -> bool:\n",
    "        if start == len(word):\n",
    "            return True\n",
    "        if vis[start]:\n",
    "            return False\n",
    "        vis[start] = True\n",
    "        node = self\n",
    "        for i in range(start, len(word)):\n",
    "            node = node.children[ord(word[i]) - ord('a')]\n",
    "            if node is None:\n",
    "                return False\n",
    "            if node.isEnd and self.dfs(word, i + 1, vis):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        words.sort(key=len)\n",
    "\n",
    "        ans = []\n",
    "        root = Trie()\n",
    "        for word in words:\n",
    "            if word == \"\":\n",
    "                continue\n",
    "            if root.dfs(word, 0, [False] * len(word)):\n",
    "                ans.append(word)\n",
    "            else:\n",
    "                root.insert(word)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.isEnd = False\n",
    "\n",
    "    def insert(self, word: str):\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ch = ord(ch) - ord('a')\n",
    "            if not node.children[ch]:\n",
    "                node.children[ch] = Trie()\n",
    "            node = node.children[ch]\n",
    "        node.isEnd = True\n",
    "\n",
    "    def dfs(self, word: str, start: int, vis: List[bool]) -> bool:\n",
    "        if start == len(word):\n",
    "            return True\n",
    "        if vis[start]:\n",
    "            return False\n",
    "        vis[start] = True\n",
    "        node = self\n",
    "        for i in range(start, len(word)):\n",
    "            node = node.children[ord(word[i]) - ord('a')]\n",
    "            if node is None:\n",
    "                return False\n",
    "            if node.isEnd and self.dfs(word, i + 1, vis):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        words.sort(key=len)\n",
    "\n",
    "        ans = []\n",
    "        root = Trie()\n",
    "        for word in words:\n",
    "            if word == \"\":\n",
    "                continue\n",
    "            if root.dfs(word, 0, [False] * len(word)):\n",
    "                ans.append(word)\n",
    "            else:\n",
    "                root.insert(word)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "#         ConcatenatedWords = []\n",
    "#         words = sorted(words, key=lambda x:len(x))\n",
    "#         # print(words)\n",
    "#         kids = []\n",
    "#         for i, w in enumerate(words):\n",
    "#             if self.wordBreak(words[i], kids):\n",
    "#                 ConcatenatedWords.append(words[i])\n",
    "#             kids.append(words[i])\n",
    "#         return ConcatenatedWords\n",
    "            \n",
    "#     def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
    "#         states = [False] * (len(s) + 1)\n",
    "#         states[0] = True\n",
    "#         if wordDict == []:\n",
    "#             return False\n",
    "#         for i in range(len(wordDict[0]), len(s)+1):\n",
    "#             for j in range(max(0, i-len(wordDict[-1])), i-len(wordDict[0])+1):\n",
    "#                 if states[j] and s[j:i] in wordDict:\n",
    "#                     states[i] = True\n",
    "#                     break\n",
    "#         return states[-1]\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.isEnd = False\n",
    "\n",
    "    def insert(self, word: str):\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ch = ord(ch) - ord('a')\n",
    "            if not node.children[ch]:\n",
    "                node.children[ch] = Trie()\n",
    "            node = node.children[ch]\n",
    "        node.isEnd = True\n",
    "\n",
    "    def dfs(self, word: str, start: int, vis: List[bool]) -> bool:\n",
    "        if start == len(word):\n",
    "            return True\n",
    "        if vis[start]:\n",
    "            return False\n",
    "        vis[start] = True\n",
    "        node = self\n",
    "        for i in range(start, len(word)):\n",
    "            node = node.children[ord(word[i]) - ord('a')]\n",
    "            if node is None:\n",
    "                return False\n",
    "            if node.isEnd and self.dfs(word, i + 1, vis):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        words.sort(key=len)\n",
    "\n",
    "        ans = []\n",
    "        root = Trie()\n",
    "        for word in words:\n",
    "            if word == \"\":\n",
    "                continue\n",
    "            if root.dfs(word, 0, [False] * len(word)):\n",
    "                ans.append(word)\n",
    "            else:\n",
    "                root.insert(word)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.childs=[None]*26\n",
    "        self.is_word=False \n",
    "    def insert(self,word):\n",
    "        node=self\n",
    "        for ch in word:\n",
    "            ch=ord(ch)-ord('a')\n",
    "            if not node.childs[ch]:\n",
    "                node.childs[ch]=Trie()\n",
    "            node=node.childs[ch]\n",
    "        node.is_word=True\n",
    "    def dfs(self,word,idx,vis):\n",
    "        if idx==len(word):return True\n",
    "        if vis[idx]:return False\n",
    "        vis[idx]=True\n",
    "        node=self#别忘了\n",
    "        for i in range(idx,len(word)):\n",
    "            node=node.childs[ord(word[i])-ord('a')]\n",
    "            if not node:return False\n",
    "            if node.is_word and self.dfs(word,i+1,vis):\n",
    "                return True\n",
    "        return False\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        #每个困难题目至少想5分钟吧\n",
    "        #暴力枚举，还要考虑不同顺序的情况和重复的情况，比如选a,b,\n",
    "        words=sorted(words,key=lambda x:len(x))\n",
    "        ans=[]\n",
    "        root=Trie()\n",
    "        for word in words:\n",
    "            if word==\"\":continue\n",
    "            if root.dfs(word,0,[False]*len(word)):\n",
    "                ans.append(word)\n",
    "            else:\n",
    "                root.insert(word)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie():\n",
    "    def __init__(self):\n",
    "        self.next=[None]*26\n",
    "        self.leaf=False\n",
    "    \n",
    "    def search(self, word: str, start: int, vis: List[bool]) -> bool:\n",
    "        if start == len(word):\n",
    "            return True\n",
    "        if vis[start]:\n",
    "            return False\n",
    "        vis[start] = True\n",
    "        node = self\n",
    "        for i in range(start, len(word)):\n",
    "            node = node.next[ord(word[i]) - ord('a')]\n",
    "            if node is None:\n",
    "                return False\n",
    "            if node.leaf and self.search(word, i + 1, vis):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    def add(self, s):\n",
    "        t=self\n",
    "        for i, c in enumerate(s):\n",
    "            if t.next[ord(c)-ord('a')] is None:\n",
    "                t.next[ord(c)-ord('a')]=Trie()\n",
    "            t=t.next[ord(c)-ord('a')]\n",
    "            if i==len(s)-1:\n",
    "                t.leaf=True\n",
    "        return\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words):\n",
    "        trie=Trie()\n",
    "        res=[]\n",
    "        words.sort(key=lambda x:len(x))\n",
    "        # print(words)\n",
    "        for word in words:\n",
    "            if trie.search(word, 0, [False] * len(word)):\n",
    "                res.append(word)\n",
    "            else:\n",
    "                trie.add(word)\n",
    "        # print(res)\n",
    "        # print(twords)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie():\n",
    "    def __init__(self):\n",
    "        self.next=[None]*26\n",
    "        self.leaf=False\n",
    "    \n",
    "    \n",
    "    def search(self, s):\n",
    "        if self.check(s): return True\n",
    "        for i in range(1,len(s)):\n",
    "            if self.check(s[:i]) and self.search(s[i:]): return True\n",
    "        return False\n",
    "\n",
    "    def check(self, s):\n",
    "        t=self\n",
    "        for i, c in enumerate(s):\n",
    "            if t.next[ord(c)-ord('a')] is not None:\n",
    "                t=t.next[ord(c)-ord('a')]\n",
    "            else:\n",
    "                return False\n",
    "        return t.leaf\n",
    "\n",
    "    def add(self, s):\n",
    "        t=self\n",
    "        for i, c in enumerate(s):\n",
    "            if t.next[ord(c)-ord('a')] is None:\n",
    "                t.next[ord(c)-ord('a')]=Trie()\n",
    "            t=t.next[ord(c)-ord('a')]\n",
    "        t.leaf=True\n",
    "        return\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words):\n",
    "        trie=Trie()\n",
    "        res=[]\n",
    "        # twords=copy.deepcopy(words)\n",
    "        words.sort(key=lambda x:len(x))\n",
    "        # print(words)\n",
    "        for word in words:\n",
    "            if trie.search(word):\n",
    "                res.append(word)\n",
    "            else:\n",
    "                trie.add(word)\n",
    "        return res\n",
    "        # print(res)\n",
    "        # print(twords)\n",
    "        # return list(filter(lambda x: x in res, twords))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.isEnd = False\n",
    "        self.children = [None] * 26\n",
    "\n",
    "    def get(self, c):\n",
    "        return self.children[ord(c)-ord('a')]\n",
    "\n",
    "    def put(self, c):\n",
    "        self.children[ord(c)-ord('a')] = TrieNode()\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "    \n",
    "    def insert(self, word):\n",
    "        p = self.root\n",
    "        for c in word:\n",
    "            if not p.get(c):\n",
    "                p.put(c)\n",
    "            p = p.get(c)\n",
    "        p.isEnd = True\n",
    "\n",
    "    def search(self, word, i):\n",
    "        if i == len(word):\n",
    "            return True\n",
    "\n",
    "        p = self.root\n",
    "        n = len(word)\n",
    "        while i < n:\n",
    "            c = word[i]\n",
    "            if not p.get(c):\n",
    "                return False\n",
    "            p = p.get(c)\n",
    "            if p.isEnd:\n",
    "                if self.search(word, i+1):\n",
    "                    return True\n",
    "            i += 1\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        words.sort(key=lambda x:len(x))\n",
    "        res = []\n",
    "        trie = Trie()\n",
    "\n",
    "        for word in words:\n",
    "            if trie.search(word, 0):\n",
    "                res.append(word)\n",
    "            else:\n",
    "                trie.insert(word)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "ida = ord('a')\r\n",
    "\r\n",
    "class Trie:\r\n",
    "    def __init__(self):\r\n",
    "        self.children = [None] * 26\r\n",
    "        self.isWord = False\r\n",
    "    def insert(self, word):\r\n",
    "        cur = self\r\n",
    "        for ch in word:\r\n",
    "            idx = ord(ch) - ida\r\n",
    "            if not cur.children[idx]:\r\n",
    "                cur.children[idx] = Trie()\r\n",
    "            cur = cur.children[idx]\r\n",
    "        cur.isWord = True\r\n",
    "    def dfs(self, word, start):\r\n",
    "        if start == len(word):\r\n",
    "            return True\r\n",
    "        cur = self\r\n",
    "        for i in range(start, len(word)):\r\n",
    "            cur = cur.children[ord(word[i])-ida]\r\n",
    "            if not cur:\r\n",
    "                return False\r\n",
    "            if cur.isWord and self.dfs(word, i+1):\r\n",
    "                return True\r\n",
    "        return False\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\r\n",
    "        words.sort(key=len)\r\n",
    "        dictTrie = Trie()\r\n",
    "        res = []\r\n",
    "        for word in words:\r\n",
    "            if not word:\r\n",
    "                continue\r\n",
    "            if dictTrie.dfs(word, 0):\r\n",
    "                res.append(word)\r\n",
    "            else:\r\n",
    "                dictTrie.insert(word)\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie():\n",
    "    def __init__(self):\n",
    "        self.next=[None]*26\n",
    "        self.leaf=False\n",
    "    \n",
    "    def search(self, s):\n",
    "        if self.check(s): return True\n",
    "        for i in range(1,len(s)):\n",
    "            if self.check(s[:i]) and self.search(s[i:]): return True\n",
    "        return False\n",
    "    \n",
    "    def check(self, s):\n",
    "        t=self\n",
    "        for c in s:\n",
    "            if t.next[ord(c)-ord('a')] is not None:\n",
    "                t=t.next[ord(c)-ord('a')]\n",
    "            else:\n",
    "                return False\n",
    "        return t.leaf\n",
    "\n",
    "    def add(self, s):\n",
    "        t=self\n",
    "        for i, c in enumerate(s):\n",
    "            if t.next[ord(c)-ord('a')] is None:\n",
    "                t.next[ord(c)-ord('a')]=Trie()\n",
    "            t=t.next[ord(c)-ord('a')]\n",
    "        t.leaf=True\n",
    "        return\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words):\n",
    "        trie=Trie()\n",
    "        res=[]\n",
    "        words.sort(key=lambda x:len(x))\n",
    "        for word in words:\n",
    "            if trie.search(word):\n",
    "                res.append(word)\n",
    "            else:\n",
    "                trie.add(word)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.isEnd = False\n",
    "        self.children = [None] * 26\n",
    "\n",
    "    def get(self, c):\n",
    "        return self.children[ord(c)-ord('a')]\n",
    "\n",
    "    def put(self, c):\n",
    "        self.children[ord(c)-ord('a')] = TrieNode()\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "    \n",
    "    def insert(self, word):\n",
    "        p = self.root\n",
    "        for c in word:\n",
    "            if not p.get(c):\n",
    "                p.put(c)\n",
    "            p = p.get(c)\n",
    "        p.isEnd = True\n",
    "\n",
    "    def search(self, word, i, visited):\n",
    "        if i == len(word):\n",
    "            return True\n",
    "        if visited[i]:\n",
    "            return False\n",
    "        visited[i] = True\n",
    "        p = self.root\n",
    "        n = len(word)\n",
    "        while i < n:\n",
    "            c = word[i]\n",
    "            if not p.get(c):\n",
    "                return False\n",
    "            p = p.get(c)\n",
    "            if p.isEnd:\n",
    "                if self.search(word, i+1, visited):\n",
    "                    return True\n",
    "            i += 1\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        words.sort(key=lambda x:len(x))\n",
    "        res = []\n",
    "        trie = Trie()\n",
    "\n",
    "        for word in words:\n",
    "            if trie.search(word, 0, [False]*len(word)):\n",
    "                res.append(word)\n",
    "            else:\n",
    "                trie.insert(word)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "ida = ord('a')\r\n",
    "\r\n",
    "class Trie:\r\n",
    "    def __init__(self):\r\n",
    "        self.children = [None] * 26\r\n",
    "        self.isWord = False\r\n",
    "    def insert(self, word):\r\n",
    "        cur = self\r\n",
    "        for ch in word:\r\n",
    "            idx = ord(ch) - ida\r\n",
    "            if not cur.children[idx]:\r\n",
    "                cur.children[idx] = Trie()\r\n",
    "            cur = cur.children[idx]\r\n",
    "        cur.isWord = True\r\n",
    "    def dfs(self, word, start, isVisited):\r\n",
    "        if start == len(word):\r\n",
    "            return True\r\n",
    "        if start in isVisited:\r\n",
    "            return False\r\n",
    "        cur = self\r\n",
    "        isVisited.add(start)\r\n",
    "        for i in range(start, len(word)):\r\n",
    "            cur = cur.children[ord(word[i])-ida]\r\n",
    "            if not cur:\r\n",
    "                return False\r\n",
    "            if cur.isWord and self.dfs(word, i+1, isVisited):\r\n",
    "                return True\r\n",
    "        return False\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\r\n",
    "        words.sort(key=len)\r\n",
    "        dictTrie = Trie()\r\n",
    "        res = []\r\n",
    "        for word in words:\r\n",
    "            if not word:\r\n",
    "                continue\r\n",
    "            if dictTrie.dfs(word, 0, set()):\r\n",
    "                res.append(word)\r\n",
    "            else:\r\n",
    "                dictTrie.insert(word)\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.isEnd = False\n",
    "\n",
    "    def insert(self, word: str):\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ch = ord(ch) - ord('a')\n",
    "            if not node.children[ch]:\n",
    "                node.children[ch] = Trie()\n",
    "            node = node.children[ch]\n",
    "        node.isEnd = True\n",
    "\n",
    "    def dfs(self, word: str, start: int, vis: List[bool]) -> bool:\n",
    "        if start == len(word):\n",
    "            return True\n",
    "        if vis[start]:\n",
    "            return False\n",
    "        vis[start] = True\n",
    "        node = self\n",
    "        for i in range(start, len(word)):\n",
    "            node = node.children[ord(word[i]) - ord('a')]\n",
    "            if node is None:\n",
    "                return False\n",
    "            if node.isEnd and self.dfs(word, i + 1, vis):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        words.sort(key=len)\n",
    "\n",
    "        ans = []\n",
    "        root = Trie()\n",
    "        for word in words:\n",
    "            if word == \"\":\n",
    "                continue\n",
    "            if root.dfs(word, 0, [False] * len(word)):\n",
    "                ans.append(word)\n",
    "            else:\n",
    "                root.insert(word)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie():\n",
    "    def __init__(self):\n",
    "        self.next=[None]*26\n",
    "        self.leaf=False\n",
    "    \n",
    "    def search(self, s):\n",
    "        if self.check(s): return True\n",
    "        for i in range(1,len(s)):\n",
    "            if self.check(s[:i]) and self.search(s[i:]): return True\n",
    "        return False\n",
    "    \n",
    "    def check(self, s):\n",
    "        t=self\n",
    "        for i, c in enumerate(s):\n",
    "            if t.next[ord(c)-ord('a')] is not None:\n",
    "                t=t.next[ord(c)-ord('a')]\n",
    "            else:\n",
    "                return False\n",
    "        return t.leaf\n",
    "\n",
    "    def add(self, s):\n",
    "        t=self\n",
    "        for i, c in enumerate(s):\n",
    "            if t.next[ord(c)-ord('a')] is None:\n",
    "                t.next[ord(c)-ord('a')]=Trie()\n",
    "            t=t.next[ord(c)-ord('a')]\n",
    "        t.leaf=True\n",
    "        return\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words):\n",
    "        trie=Trie()\n",
    "        res=[]\n",
    "        words.sort(key=lambda x:len(x))\n",
    "        for word in words:\n",
    "            if trie.search(word):\n",
    "                res.append(word)\n",
    "            else:\n",
    "                trie.add(word)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None]*26\n",
    "        self.isEnd = False\n",
    "\n",
    "    def insert(self, word: str):\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ch = ord(ch) - ord('a')\n",
    "            if not node.children[ch]:\n",
    "                node.children[ch] = Trie()\n",
    "            node = node.children[ch]\n",
    "        node.isEnd = True\n",
    "\n",
    "    def dfs(self, word:str, start: int, vis: List[bool]) -> bool:\n",
    "        if start == len(word):\n",
    "            return True\n",
    "        if vis[start]:\n",
    "            return False\n",
    "        vis[start] = True\n",
    "        node = self\n",
    "        for i in range(start, len(word)):\n",
    "            node = node.children[ord(word[i])-ord('a')]\n",
    "            if node is None:\n",
    "                return False\n",
    "            if node.isEnd and self.dfs(word, i + 1, vis):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        words.sort(key=len)\n",
    "        \n",
    "        ans = []\n",
    "        root = Trie()\n",
    "        for word in words:\n",
    "            if word == \"\":\n",
    "                continue\n",
    "            if root.dfs(word, 0, [False] * len(word)):\n",
    "                ans.append(word)\n",
    "            else:\n",
    "                root.insert(word)\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self) -> None:\n",
    "        self.children = [None] * 26\n",
    "        self.is_end = False\n",
    "\n",
    "    def insert(self, word: str):\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ch = ord(ch) - ord('a')\n",
    "            if not node.children[ch]:\n",
    "                node.children[ch] = Trie()\n",
    "            node = node.children[ch]\n",
    "        node.is_end = True\n",
    "\n",
    "    def dfs(self, word: str, start: int, vis: List[bool]) -> bool:\n",
    "        if start == len(word):\n",
    "            return True\n",
    "        if vis[start]:\n",
    "            return False\n",
    "        vis[start] = True\n",
    "        node = self\n",
    "        for i in range(start, len(word)):\n",
    "            node = node.children[ord(word[i]) - ord('a')]\n",
    "            if node is None:\n",
    "                return False\n",
    "            if node.is_end and self.dfs(word, i+1, vis):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        words.sort(key = len)\n",
    "        ans = []\n",
    "        root = Trie()\n",
    "        for word in words:\n",
    "            if word == \"\":\n",
    "                continue\n",
    "            if root.dfs(word,0,[False] * len(word)):\n",
    "                ans.append(word)\n",
    "            else:\n",
    "                root.insert(word)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.isEnd = False\n",
    "\n",
    "    def insert(self, word: str):\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ch = ord(ch) - ord('a')\n",
    "            if not node.children[ch]:\n",
    "                node.children[ch] = Trie()\n",
    "            node = node.children[ch]\n",
    "        node.isEnd = True\n",
    "\n",
    "    def dfs(self, word: str, start: int, vis: List[bool]) -> bool:\n",
    "        if start == len(word):\n",
    "            return True\n",
    "        if vis[start]:\n",
    "            return False\n",
    "        vis[start] = True\n",
    "        node = self\n",
    "        for i in range(start, len(word)):\n",
    "            node = node.children[ord(word[i]) - ord('a')]\n",
    "            if node is None:\n",
    "                return False\n",
    "            if node.isEnd and self.dfs(word, i + 1, vis):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        words.sort(key=len)\n",
    "\n",
    "        ans = []\n",
    "        root = Trie()\n",
    "        for word in words:\n",
    "            if word == \"\":\n",
    "                continue\n",
    "            if root.dfs(word, 0, [False] * len(word)):\n",
    "                ans.append(word)\n",
    "            else:\n",
    "                root.insert(word)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.isEnd = False\n",
    "\n",
    "    def insert(self, word: str):\n",
    "        node = self\n",
    "        for ch in word:\n",
    "            ch = ord(ch) - ord('a')\n",
    "            if not node.children[ch]:\n",
    "                node.children[ch] = Trie()\n",
    "            node = node.children[ch]\n",
    "        node.isEnd = True\n",
    "\n",
    "    def dfs(self, word: str, start: int, vis: List[bool]) -> bool:\n",
    "        if start == len(word):\n",
    "            return True\n",
    "        if vis[start]:\n",
    "            return False\n",
    "        vis[start] = True\n",
    "        node = self\n",
    "        for i in range(start, len(word)):\n",
    "            node = node.children[ord(word[i]) - ord('a')]\n",
    "            if node is None:\n",
    "                return False\n",
    "            if node.isEnd and self.dfs(word, i + 1, vis):\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n",
    "        words.sort(key=len)\n",
    "\n",
    "        ans = []\n",
    "        root = Trie()\n",
    "        for word in words:\n",
    "            if word == \"\":\n",
    "                continue\n",
    "            if root.dfs(word, 0, [False] * len(word)):\n",
    "                ans.append(word)\n",
    "            else:\n",
    "                root.insert(word)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "ida = ord('a')\r\n",
    "\r\n",
    "class Trie:\r\n",
    "    def __init__(self):\r\n",
    "        self.children = [None] * 26\r\n",
    "        self.isWord = False\r\n",
    "    def insert(self, word):\r\n",
    "        cur = self\r\n",
    "        for ch in word:\r\n",
    "            idx = ord(ch) - ida\r\n",
    "            if not cur.children[idx]:\r\n",
    "                cur.children[idx] = Trie()\r\n",
    "            cur = cur.children[idx]\r\n",
    "        cur.isWord = True\r\n",
    "\r\n",
    "    def dfs(self, word, start):\r\n",
    "        if start == len(word):\r\n",
    "            return True\r\n",
    "        cur = self\r\n",
    "        for i in range(start, len(word)):\r\n",
    "            cur = cur.children[ord(word[i])-ida]\r\n",
    "            if not cur:\r\n",
    "                return False\r\n",
    "            if cur.isWord and self.dfs(word, i+1):\r\n",
    "                return True\r\n",
    "        return False\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\r\n",
    "        words.sort(key=len)\r\n",
    "        dictTrie = Trie()\r\n",
    "        res = []\r\n",
    "        for word in words:\r\n",
    "            if not word:\r\n",
    "                continue\r\n",
    "            if dictTrie.dfs(word, 0):\r\n",
    "                res.append(word)\r\n",
    "            else:\r\n",
    "                dictTrie.insert(word)\r\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
